/*
 * @lc app=leetcode.cn id=122 lang=java
 *
 * [122] 买卖股票的最佳时机 II
 */

// @lc code=start
//基于贪心思想
// class Solution {
//     public int maxProfit(int[] prices) {
//         int sum=0;
//         for(int i=0;i<prices.length-1;i++){
//             sum+=Math.max(prices[i+1]-prices[i], 0);
//         }
//         return sum;

//     }
// }
//基于动态规划
class Solution {
    public int maxProfit(int[] prices) {
        //相比较121题目，这里区别在于dp[i][1]持有时的最大利润推导公式：
        //dp[i][1]可以由第i-1天持有，第i天保持；第i-1天不持有，第i天买入
        //dp[i][1]=Math.max(dp[i-1][1],dp[i-1][0]-prices[i]);这里dp[i-1][0]不持有可能也有之前的利润
        int[][] dp=new int[2][2];
        dp[0][0]=0;
        dp[0][1]=-prices[0];
        for(int i=1;i<prices.length;i++){
            dp[i%2][0]=Math.max(dp[(i-1)%2][0],dp[(i-1)%2][1]+prices[i]);
            dp[i%2][1]=Math.max(dp[(i-1)%2][1],dp[(i-1)%2][0]-prices[i]);
        }
        return dp[(prices.length-1)%2][0];
    }
}

// @lc code=end

